25. 一次线性同余方程组的解数公式

一次线性同余方程组 $a_{1} x_{1} + \dots + a_{k} x_{k} \equiv b (\mod m)$ 的解数为 $m^{k - 1} d [d ∣ b]$ ，其中 $d = (a_{1}, \dots, a_{k}, m)$ .

证明.

用 OI 的话说，我们来进行单位根反演。

\sum_{x = 0}^{m - 1} ω_{m}^{c x} = m [m ∣ c]

这个式子起到了一个检验是否整除的效果。

那么我们直接枚举每个变量的取值，容易发现解数为

\begin{aligned} T & = \frac{1}{m} \sum_{c = 0}^{m - 1} \sum_{x_{1} = 0}^{m - 1} \dots \sum_{x_{k} = 0}^{m - 1} ω_{m}^{c (a_{1} x_{1} + \dots + a_{k} x_{k} - b)} \\ = m^{k - 1} \sum_{c = 0}^{m - 1} ω_{m}^{- b c} [m ∣ c a_{1}] \dots [m ∣ c a_{k}] \\ = m^{k - 1} \sum_{c = 0}^{m - 1} ω_{m}^{- b c} [m ∣ c (a_{1}, \dots, a_{k})] \\ = m^{k - 1} \sum_{c = 0}^{m - 1} ω_{m}^{- b c} [\frac{m}{d} ∣ c] \end{aligned}

到这一步枚举 $c = t \frac{m}{d}$ ，易得 $t = 0, 1, \dots, d - 1$ ，故

\begin{aligned} T & = m^{k - 1} \sum_{t = 0}^{d - 1} ω_{m}^{- b t m / d} \\ = m^{k - 1} \sum_{t = 0}^{d - 1} ω_{d}^{- b t} \\ = m^{k - 1} d [d ∣ b] \end{aligned}

证毕。

练习. 证明：

\sum_{k = 0}^{n} (\binom{4 n + 1}{4 k + 1}) = 2^{4 n - 1} + (- 1)^{n} 2^{2 n - 1}

注. 实际上不定方程的解数也能有类似的表示，关键是

\int_{0}^{1} \exp (2 π i c x) = [c = 0]